package com.breeze.sort;

/**
 * 一、冒泡排序
 * 1. 比较相邻元素，大着放在后边，对于元素一次遍历即可确定一个最大值
 * 2. 比较 length-1 轮，即可使所有元素按照从小到大排列
 * <p>
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */
public class BubbleSort implements Sort {

    @Override
    public void sort(int[] arr) {
        // length个元素，共需要length-1次确定无序元素中的最大值
        for (int i = 0; i < arr.length - 1; i++) {
            // 对无序元素进行比较，相邻元素大数靠后放置;注意已排序好的无序比较，故 length-1-i
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
}
